// 17.07. 婴儿名字/面试题/并查集
// https://leetcode-cn.com/problems/baby-names-lcci
// sscanf(sy.c_str(), "(%[^,]s,%[^)]s)", name1, name2); //错误,前面的s删除
// 每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。
// 有些名字有多种拼法，例如，John 和 Jon
// 本质上是相同的名字，但被当成了两个名字公布出来。
// 给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。
// 设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，
// 并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
// 在结果列表中，选择 字典序最小 的名字作为真实名字。
// 输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"],
// synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
// 输出：["John(27)","Chris(36)"]
   
#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
  map<string, string> mapParent_;  // p[child] = parent
  string findParent(const string& na) {
    if (mapParent_[na] != na) {
      mapParent_[na] = findParent(mapParent_[na]);
    }
    return mapParent_[na];
  }
  void unionNode(const string& n1, const string& n2) {
    mapParent_[findParent(n1)] = findParent(n2);
  }

 public:
  // names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"],
  // synonyms =
  // ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
  // 输出：["John(27)","Chris(36)"]
  vector<string> trulyMostPopular(vector<string> names,
                                  vector<string> synonyms) {
    // self
    for (auto tmp : names) {
      char name[64] = {0};
      char sFreq[64] = {0};
      sscanf(tmp.c_str(), "%[^(](%s)", name, &sFreq);
      mapParent_[name] = name;
    }
    for (auto sy : synonyms) {
      char name1[64] = {0};
      char name2[64] = {0};
      sscanf(sy.c_str(), "(%[^,],%[^)]s)", name1, name2);
      mapParent_[name1] = name1;
      mapParent_[name2] = name2;
    }
    // union
    for (auto sy : synonyms) {
      char name1[64] = {0};
      char name2[64] = {0};
      sscanf(sy.c_str(), "(%[^,],%[^)]s)", name1, name2);
      unionNode(name1, name2);
    }
    // synonyms to set
    map<string, set<string> > mapSynonyms;  //  parentName, set_name 同名集
    map<string, int> mapFreq;               // name, freq
    for (auto [name, parentName] : mapParent_) {
      mapSynonyms[findParent(parentName)].insert(name);
    }
    // statistics freq
    for (auto tmp : names) {
      char name[64] = {0};
      char sFreq[64] = {0};
      sscanf(tmp.c_str(), "%[^(](%s)", name, &sFreq);
      string trueName = *mapSynonyms[findParent(name)].begin();
      mapFreq[trueName] += atoi(sFreq);
    }
    vector<string> res;
    for (auto [name, freq] : mapFreq) {
      char sTmp[128] = {0};
      sprintf(sTmp, "%s(%d)", name.c_str(), freq);
      res.push_back(sTmp);
    }
    return res;
  }
};

int main() {
  Solution sol;
  auto vtOut = sol.trulyMostPopular(
      {"John(15)", "Jon(12)", "Chris(13)", "Kris(4)", "Christopher(19)"}, {});
  //                                      {"(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"});
  for (auto n : vtOut) PF("%s,  ", n.c_str());
  PF("\n");
  return 0;
}
